package chapter03;


public class IsBalanced110 {
    /**
     * 树形dp
     * 如果知道左右子树是否是平衡二叉树和左右子树的高度 那么我们就可以返回以x为根节点的信息
     * 因为需要知道子树高度和子树是否是平衡二叉树 需要两个信息 将这两个信息包装成一个类
     * Info :int height、boolean isBT
     * process(x) 处理以x为根的子树
     * 递归出口
     * 1).x==null
     *      return new Info(0,true)
     * 2).其他情况
     *      leftInfo=process(x.left)
     *      leftInfo=process(x.left)
     *      height=max(leftInfo.height,rightInfo.height)+1
     *      isBt=false
     *      if   leftInfo.isBT&&rightInfo.isBT&&abs(leftInfo.height-rightInfo.height)<=1
     *          isBT=true
     *      return new Info(height,isBT)
     */
     public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }
   public class Info{
         public int height;
         public boolean isBT;

       public Info(int height, boolean isBT) {
           this.height = height;
           this.isBT = isBT;
       }
   }

    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        return process(root).isBT;
    }

    public Info process(TreeNode x){
         if(x==null){
             return new Info(0,true);
         }
         Info leftInfo=process(x.left);
         Info rightInfo=process(x.right);
         boolean isBT=false;
         int height=Math.max(leftInfo.height,rightInfo.height)+1;
         if(leftInfo.isBT &&rightInfo.isBT&&Math.abs(leftInfo.height- rightInfo.height)<=1){
             isBT=true;
         }
         return new Info(height,isBT);
    }
}
